class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.count = 1;
    };
    show() {
        return this.data;
    }

}
class BinarySearchTree {
    constructor() {
        this.root = null;
    };
    // 插入节点
    insert(data) {
            let n = new Node(data, null, null);
            if (this.root == null) {
                this.root = n;
            } else {
                let currNode = this.root;
                let parNode;
                while (true) {
                    parNode = currNode;
                    if (data < currNode.data) {
                        currNode = currNode.left;
                        if (currNode == null) {
                            parNode.left = n;
                            break
                        }
                    } else {
                        currNode = currNode.right;
                        if (currNode == null) {
                            parNode.right = n;
                            break
                        }
                    }
                }
            }
        }
        // 中序遍历
    inOrder(node) {
            if (node != null) {
                this.inOrder(node.left);
                console.log(node.show() + '');
                this.inOrder(node.right)
            }
        }
        // 先序遍历
    preOrder(node) {
            if (node != null) {
                console.log(node.show() + '');
                this.preOrder(node.left);
                this.preOrder(node.right)
            }
        }
        // 后序遍历
    postOrder(node) {
        if (node != null) {
            this.postOrder(node.left);
            this.postOrder(node.right);
            console.log(node.show() + '');
        }
    }
    getMin() {
        let currNode = this.root;
        while (currNode != null) {
            currNode = currNode.left;
        };
        return currNode.data
    }
    getMax() {
        let currNode = this.root;
        while (currNode != null) {
            currNode = currNode.right;
        };
        return currNode.data
    }
    find(data) {
        let currNode = this.root;
        while (currNode != null) {
            if (currNode.data == data) {
                return currNode
            } else if (data < currNode.data) {
                currNode = currNode.left;
            } else {
                currNode = currNode.right;
            }
        }
        return null
    }

    remove(data) {
        root = removeNode(this.root, data);
    };
    removeNode(node, data) {
        if (node === null) {
            return null
        } else if (data == node.data) {
            if (node.left == null && node.right == null) {
                return null
            } else if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                let tempNode = this.getMin(node.right);
                node.data = tempNode.data;
                node.right = this.removeNode(node.right, node.data);
                return node;
            }
        } else if (data < node.data) {
            node.left = this.removeNode(node.left, data);
            return node;
        } else {
            node.right = this.removeNode(node.right, data);
            return node;
        }
    };
    update(data) {
        let grade = this.find(data);
        grade.count++;
        return grade
    };
    // 广度优先遍历
    widthOrder(node) {
        if (node === null) {
            return []
        };
        let res = [];
        let stack = [node];
        while (stack.length) {
            let node = stack.shift();
            if (node.left) {
                stack.push(node.left)
            };
            if (stack.right) {
                stack.push(node.right)
            };
            res.push(node.val)
        };
        return res
    };
    // 深度优先算法
    deepOrder(node) {
        if (node === null) {
            return []
        };
        let res = [];
        let stack = [node];
        while (stack.length) {
            let node = stack.shift();
            res.push(node.val);
            if (node.right) {
                stack.unshift(node.right)
            };
            if (stack.left) {
                stack.unshift(node.left)
            };
        }
    }
}